{
 "nbformat": 4,
 "nbformat_minor": 2,
 "metadata": {
  "language_info": {
   "name": "python",
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "version": "3.7.3-final"
  },
  "orig_nbformat": 2,
  "file_extension": ".py",
  "mimetype": "text/x-python",
  "name": "python",
  "npconvert_exporter": "python",
  "pygments_lexer": "ipython3",
  "version": 3,
  "kernelspec": {
   "name": "python37364bit81428472ef7646d5adb82b4bacf35110",
   "display_name": "Python 3.7.3 64-bit"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 数组合并\n",
    "#### - 合并有序数组\n",
    "\n",
    "有两个升序数组：\n",
    "\n",
    "\\[1, 3, 4, 6, 10\\]\n",
    "\n",
    "\\[2, 5, 8, 11\\]\n",
    "\n",
    "要将他们合并成新的一个升序数组"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": "[1, 2, 3, 4, 5, 6, 8, 10, 11]\n"
    }
   ],
   "source": [
    "array1 = [1,3,4,6,10]\n",
    "array2 = [2,5,8,11]\n",
    "arr = []\n",
    "\n",
    "# arrays above are originally in ascending order\n",
    "length = max( len(array1), len(array2) )\n",
    "while array1 != [] or array2 != []:\n",
    "    if array1 == []:\n",
    "        arr = arr + array2\n",
    "        break\n",
    "    elif array2 == []:\n",
    "        arr = arr + array2\n",
    "        break\n",
    "    else:\n",
    "        minim = min(array1[0], array2[0])\n",
    "        arr.append(minim)\n",
    "        if array1[0] == minim:\n",
    "            array1.remove(minim)\n",
    "            continue\n",
    "        elif array2[0] == minim:\n",
    "            array2.remove(minim)\n",
    "            continue\n",
    "print(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": "[1, 2, 3, 4, 5, 6, 8, 10, 11]\n"
    }
   ],
   "source": [
    "array1 = [1,3,4,6,10]\n",
    "array2 = [2,5,8,11]\n",
    "arr = array1.copy()\n",
    "index = 0\n",
    "\n",
    "# use every item in &array2 to traverse &array1\n",
    "# while-else statement\n",
    "# while-judgement:False -> else; \n",
    "# break -> jump out both while-module and else-module\n",
    "for item in range(0, len(array2)):\n",
    "    while index in range(0, len(array1)):\n",
    "        if array1[index] < array2[item]:\n",
    "            index += 1\n",
    "        else:\n",
    "            arr.insert(index+item, array2[item])\n",
    "            break\n",
    "    else:\n",
    "        arr = arr + array2[item:]\n",
    "print(arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 二分查找\n",
    "\n",
    "#### - 二分查找是针对有序数组的"
   ]
  }
 ]
}